package com.yuan.algorithms.面试题;

import java.util.Scanner;

/**
 * 输入两个整数a和b，请输出a+b的结果，不能使用加号，包括调用的函数内也不能有加法运算。（-999999999 <= a,b <= 999999999）
 * 示例
 * 输入：
 * 15 33
 * 输出
 * 48
 * 输入：
 * -999999999 999999999
 * 输出
 * 0
 * @author YouYuan
 * @date 2022/3/27 15:08
 */
public class 不使用加号实现整数加法 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            long sum = add(a, b);
            long minus = sub(a, b);
            System.out.println(a + "+" + b + "=" + sum);
            System.out.println(a + "-" + b + "=" + minus);
        }
    }

    /**
     * 使用位运算实现整数的加法，先将数字转换为二进制的形式，便于理解
     * 例如3+5，二进制表示为11+101
     * 1^1=0,0^1=1,0^0=0，根据异或的运算规则，可以使用异或运算来计算数字的相加结果
     * 1&1=1,1&0=0,0&0=0，根据与运算的规则，可以使用与运算来计算数字的进位结果
     * 3+5的二进制异或运算加法过程：
     * 11 ^ 101 = 110(和)
     * 11 & 101 = 001(进位数)
     * 001 << 1 = 10(进位操作)
     * 110 ^ 10 = 100(累加和)
     * 110 & 10 = 10(计算进位数)
     * 10 << 1 = 100(进位操作)
     * 100 ^ 100 = 011(累加和)
     * 100 & 100 = 100(计算进位数)
     * 100 << 1 = 1000(进位操作)
     * 011 ^ 1000 = 1000(累加和)
     * 011 & 1000 = 0(没有进位了，计算结束)
     * 计算出3+5的最终结果为1000(二进制)=8(十进制)
     * @param a
     * @param b
     * @return
     */
    private static long add(long a, long b) {
        long sum = a ^ b;//a+b的结果(无进位)
        long scale = a & b;//a+b的进位
        long temp = sum;//临时存储a+b的值
        while (scale != 0) {//判断进位存在
            scale <<= 1;//进行进位操作
            temp = sum ^ scale;//计算加上进位之后的结果，因为sum还需要和scale进行计算，所以先用临时变量保存
            scale = sum & scale;//计算下一次进位
            sum = temp;
        }
        return sum;
    }

    /**
     * 使用位运算实现减法
     * a-b相当于a+(-b)
     * 使用非运算~可以实现二进制数的取反，例如
     * 1(十进制)取反之后的值为11111111111111111111111111111110(二进制)，十进制为-2
     * 10(十进制)取反之后的值为11111111111111111111111111110101(二进制)，十进制为-11
     * 也就是说a+(-b)=a+(~b+1)
     * @param a
     * @param b
     * @return
     */
    private static long sub(long a, long b) {
        return add(a, add(~b, 1));
    }
}
